package com.gs.coursera.algorithms.core.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class DepthFirstPath<T, W extends Comparable<W>> extends Path<T, W>{

	private Stack<Vertex<T, W>> path = new Stack<Vertex<T, W>>();
	
	public DepthFirstPath(Graph<T, W> graph, T source) {
		super(graph, source);
	}

	@Override
	public boolean hasPathTo(Vertex<T, W> to) {
		return to.isExplored();
	}

	@Override
	public Iterable<Vertex<T, W>> pathTo(Vertex<T, W> v) {
		if (!hasPathTo(v)) 
			return null;
		List<Vertex<T, W>> walk = new ArrayList<Vertex<T,W>>();
		Stack<Vertex<T, W>> stack = new Stack<Vertex<T,W>>();
		stack.push(getSourceVertex());
		walk.add(getSourceVertex());
		while(!stack.isEmpty()){
			Vertex<T, W> t = stack.peek();
			if(t.equals(v)){
				walk.add(t);
				return walk;
			}
			for(Edge<T,W> e : t.getAdjacencyList()){
				if(e.isTreeEdge()){
					Vertex<T, W> w = e.getEndVertex();
					if(w.isExplored()){
						walk.add(w);
						stack.push(w);
					}
					continue;
				}
			}
			stack.pop();
		}
		return walk;
	}

	/**
	 * Implementation of DFS
	 */
	@Override
	public void doSearch(Graph<T, W> graph, Vertex<T, W> source) {
		source.setDiscovered(true);
		for(Edge<T,W> e : source.getAdjacencyList()){
			if(!e.isLabled()){
				Vertex<T, W> w = e.getEndVertex();
				if(!w.isExplored()){
					e.setTreeEdge(true);
					doSearch(graph, w);
				} else {
					e.setBackEdge(true);
				}
			}
		}
		source.setExplored(true);
		/*
		for(Vertex<T, W> x : graph.getAdjacencyList(source)){
			if(!x.isDiscovered()){
				getEdgeWalk().add(x);
				doSearch(getGraph(), x);
			}
		}*/
	}
	
	public void iterativeDfs(Graph<T, W> graph, Vertex<T, W> source){
		source.setDiscovered(true);
		Stack<Vertex<T, W>> stack = new Stack<Vertex<T,W>>();
		stack.push(source);
		while(!stack.isEmpty()){
			Vertex<T, W> t = stack.peek();
			for(Edge<T,W> e : t.getAdjacencyList()){
				if(e.isLabled()){
					continue;
				}
				Vertex<T, W> w = e.getEndVertex();
				if(!w.isDiscovered() && !w.isExplored()){
					e.setTreeEdge(true);
					w.setDiscovered(true);
					stack.push(w);
					continue;
				} else if(w.isDiscovered()){
					e.setBackEdge(true);
				} else {
					e.setCrossEdge(true);
				}
			}
			t.setExplored(true);
			stack.pop();
		}
	}
	
}
